package com.algrithom.dp;

import java.util.Objects;

public class Solution1 {
    
    public static void main(String[] args){
        System.out.println(longestSubStr(")()()()"));
        System.out.println(longestSubStr(")()()"));
        System.out.println(longestSubStr(")(())"));
        System.out.println(longestSubStrOther(")(())"));
    }
    
    private static int longestSubStr(String str){
        if (Objects.isNull(str) || str.length() == 0) {
            return 0;
        }
        int len = str.length();
        int result = 0;
        char[] chars = str.toCharArray();
        int[] dp = new int[len];
        for (int i = 1; i < len; i++) {
            if (chars[i] == ')') {
                if (chars[i - 1] == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && chars[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + 2;
                    if (i - dp[i - 1] >= 2) {
                        dp[i] = dp[i] + dp[i - dp[i - 1] - 2];
                    }
                }
                result = Math.max(result,dp[i]);
            }
        }
        return result;
    }
    
    private static int longestSubStrOther(String str){
        int len = str.length();
        char[] chars = str.toCharArray();
        int left = 0;
        int right = 0;
        int result = 0;
        // ())
        for (int i = 0; i < len; i++) {
            if (chars[i] == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                result = Math.max(result,2 * right);
            } else if (right >= left) {
                left = 0;
                right = 0;
            }
        }
        left = 0;
        right = 0;
        // (()
        for (int i = len - 1; i >= 0; i--) {
            if (chars[i] == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                result = Math.max(result,2 * left);
            } else if (left >= right) {
                left = 0;
                right = 0;
            }
        }
        return result;
    }
}
